package com.hsc.offer;

/**
 * @author
 * @date 2025-07-04
 * @Description //输入两个整数序列，第一个序列表示栈的压入顺序，
 * // 请判断第二个序列是否可能为该栈的弹出顺序。
 * // 假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，
 * // 序列4,5,3,2,1是该压栈序列对应的一个弹出序列，
 * // 但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
 */
public class OfferTest16 {
    public static void main(String[] args) {
        OfferTest16 offerTest16 = new OfferTest16();
        int[] pushA = {1, 2, 3, 4, 5};
        int[] popA = {4, 5, 3, 2, 1};
        System.out.println("offerTest16.IsPopOrder(pushA, popA) = " + offerTest16.IsPopOrder(pushA, popA));
    }

    public boolean IsPopOrder(int[] pushA, int[] popA) {
        // 创建一个数组+指针 模拟出一个栈
        int[] stack = new int[pushA.length];
        // 栈的指针
        int stackPointer = 0;
        // pushA 数组的指针 用于将放入数组的序列一个个的放入
        int pushPointer = 0;
        // 弹出序列的指针
        int popPointer = 0;

        while (true) {
            // 元素入栈
            // 最开始肯定会先进入这个条件 stackPointer  <= 0 就会进入循环   stack[stackPointer - 1] 不会执行 也就不会出现数组越界问题
            // stackPointer <= 0 代表栈是空的 需要往栈里面放元素
            // popA[popPointer]  弹出的序列的中的元素
            // stack[stackPointer - 1] => 指向的是栈的最大值
            // 如果弹出序列中的元素跟栈的最大值比较不相等，继续往栈放元素，一直比较
            if (stackPointer <= 0 || popA[popPointer] != stack[stackPointer - 1]) {
                // 表示能放入的元素 都已经全部放到栈中了 放完了
                if (pushPointer >= pushA.length) {
                    return false;
                }
                // 压入新元素并移动指针
                // 将pushA 中的元素放入模拟的栈的中
                stack[stackPointer] = pushA[pushPointer];
                // 继续放元素  stackPointer和pushPointer 对应增加
                stackPointer++; // 栈的指针递增
                pushPointer++; // 压栈序列的指针 继续往队列后移动
            }
            // 将上面放入栈的元素出栈 并且跟弹出栈的序列进行比较
            if (popA[popPointer] == stack[stackPointer - 1]) {
                popPointer++; // 表示弹出的栈的元素 比较完一个 进行递增 下一个弹栈的元素
                stackPointer--;// 代表出栈了一个元素 进行递减
                // 弹出序列已全部匹配 弹栈的元素跟栈的元素全部比较完了
                if (popPointer >= popA.length) {
                    return true;
                }
            }
        }
    }
}
